//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2  奇数n/2+1, 偶数 n/2；n/2+1
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治 
// 👍 4254 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }

        int m = nums1.length, n = nums2.length;
        int left_num_total = (m + n + 1) / 2;

        int left = 0, right = m;
        int median1 = 0, median2 = 0;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = left_num_total - i;

            int nums1_a = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1_b = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int nums2_a = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int nums2_b = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (nums1_a <= nums2_b) {
                median1 = Math.max(nums1_a, nums2_a);
                median2 = Math.min(nums1_b, nums2_b);
                left = left + 1;
            } else {
                right = right - 1;
            }
        }
        return ((m+n) % 2 == 0) ? (median1 + median2) / 2.:median1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
